package algorithm.monotonousStack;

public class SumOfSubarrayMinimums {

    public static int subArrayMinSum1(int[] arr){
        long sum = 0;
        int[] stack = new int[arr.length];
        int last = -1;
        for (int i = 0; i < arr.length; i++) {
            while(last != - 1 && arr[stack[last]] >=arr[i]){
                int pop = stack[last--];
                int start = last == -1? -1 : stack[last];
                int mid = pop;
                int end = i - 1;
                sum += (mid - start) * (end - mid + 1) * (long)arr[mid];
            }
            stack[++last] = i;
        }
        while(last != -1){
            int pop = stack[last--];
            int start = last == -1? -1 : stack[last];
            int mid = pop;
            int end = arr.length - 1;
            sum += (mid - start) * (end - mid + 1) * (long)arr[mid];
        }
        return (int) (sum % (1000000007));
    }

    public static void main(String[] args) {

    }
}
